COMMENT ⊗   VALID 00014 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002			HOMOMORPHISMS OF SEMANTIC TREES
C00005 00003		3.)  If < N1 , L1 > and < N2 , L2 > occur at mate arcs of T1
C00008 00004	
C00011 00005	distinguished clause graphs  and mate pair  graphs of T1 and  T2 will
C00014 00006	clauses, namely  C1 and C2,  are mapped onto  D by  the homomorphism.
C00017 00007		Definition: An πautomorphism is a  homomorphism of a semantic
C00020 00008		Theorem  (Images  of  Continuous  Paths):   The  image  of  a
C00022 00009	argument, and similarly for the right subtree of T.  The theorem then
C00024 00010		Theorem  (Images of  Closed  Sets under  Homomorphisms):  The
C00027 00011		Corollary (Closed  Sets  and Complete  Trees without  Vacuous
C00030 00012		Corollary:  Any  distinguished  literal   automorphism  of  a
C00032 00013		2.)  For every index i such that some distinguished literal in T2
C00034 00014		Definition: A  πmapping πof  πarcs from  semantic tree T1  to
C00038 ENDMK
C⊗;
		HOMOMORPHISMS OF SEMANTIC TREES

	We have  discussed orderings on  semantic trees and  paths in
semantic trees.   Now we discuss homomorphisms.   A homomorphism is a
mapping from the distinguished literals  of one semantic tree to  the
distinguished  literals  of  another  semantic  tree  that  preserves
certain  structure.   Intuitively,  the  same instances  of  the same
clauses are used in both trees, and the same literals resolve against
one another.   However, the mapping need not be  one-to-one.  In this
section we  will investigate  the  relationship of  homomorphisms  to
orderings, paths, and graphs of semantic trees. 

	Definition: A πhomomorphism  πof πtips from semantic  tree T1
to semantic tree T2 is a mapping f from the tips of T1 to the tips of
T2 satisfying the following requirements:

	1.)  For a tip node N of T1, the clause at N must be identical
	     to the clause at f(N) in T2.

	2.)  If distinguished literal < N , L1 > occurs at arc A1 in
	     T1 and distinguished literal < f(N) , L1 > occurs at arc A2
	     in T2, then the labels of A1 and A2 must be identical.

	3.)  If < N1 , L1 > and < N2 , L2 > occur at mate arcs of T1
	     then < f(N1) , L1 > and < f(N2) , L2 > must occur at mate
	     arcs of T2.

	Definition: The distinguished  literal mapping πinduced  by a
homomorphism f  of tips from semantic tree T1  to semantic tree T2 is
the mapping which maps distinguished literal < N , L > of T1 onto the
distinguished literal < f(N) , L > of T2. 

	Definition:  A  πdistinguished  πliteral  πhomomorphism  from
semantic  tree  T1  to semantic  tree  T2  is a  mapping  g  from the
distinguished literals of T1 to the distinguished literals of T2 such
that there exists a tip homomorphism f from T1 to T2 which induces g.
The author  suspects but  cannot prove  that such  a mapping  between
complete semantic trees without vacuous arcs is unique if it exists. 

	Definition: The  distinguished clause  mapping πinduced by  a
tip  homomorphism f  from  T1 to  T2 is  the  mapping which  maps the
distinguished clause  at tip  node  N in  T1 onto  the  distinguished
clause at f(N) in T2. 

	Definition:  A  πdistinguished   πclause  πhomomorphism  from
semantic  tree  T1  to semantic  tree  T2  is a  mapping  g  from the
distinguished clauses of T1  to the distinguished clauses of  T2 such
that there exists a tip homomorphism f from T1 to T2 which induces g. 

	Definition:  The  mate   pair  mapping  πinduced  by   a  tip
homomorphism  f from  semantic tree  T1  to semantic  tree T2  is the
mapping which maps mate pair (L1 , L2) of T1 onto mate pair  (g(L1) ,
g(L2)) of T2, where g is the distinguished literal mapping induced by
f. 

	Definition: A πmate πpair πhomomorphism from semantic tree T1
to semantic tree T2 is a  mapping g from the mate pairs of T1  to the
mate pairs of T2 such  that there exists a tip homomorphism f from T1
to T2 which induces g. 

	Similarly, we may define  the mate pair homomorphism  induced
by a distinguished  literal homomorphism, and  so on.   These various
concepts  of homomorphism  are  largely  interchangeable.   We  shall
mainly  be concerned  with distinguished literal  homomorphisms.  The
term πhomomorphism will refer to a distinguished literal homomorphism
unless otherwise specified. 

	Definition:  A  πdistinguished  πliteral  πisomorphism  is  a
distinguished literal homomorphism that is 1-1 and onto.  If there is
a distinguished literal isomorphism  from T1 to T2, then  we say that
T1  and T2 are  πdistinguished πliteral  πisomorphic.  Note  that the
distinguished clause graphs  and mate pair  graphs of T1 and  T2 will
also  be isomorphic, in this  case.  Also, note  that a distinguished
literal isomorphism is not the same as a πnode isomorphism, which was
presented  in an earlier  section.   In the following  discussion, we
will just refer to 1-1 homomorphisms onto semantic trees, rather than
isomorphisms. 

	Now  we   give  an   example  of   a  distinguished   literal
homomorphism  that is  not 1-1.   See figure  4.1.   Also, we  give a
slightly non-trivial example of a distinguished literal isomorphism. 
See figure 4.3.  The following conventions will  be used in these and
later illustrations:

	By C.L we indicate the distinguished literal < N , L > of the
distinguished clause C, where N is  the tip node at which C  occurs. 
We  draw such  distinguished literals  near  the arcs  at which  they
occur.   We sometimes label tip  nodes with the distinguished clauses
that occur there.  We indicate homomorphisms by  specifying where the
distinguished  clauses  are mapped  under  the induced  distinguished
clause mapping.  Thus, C → D indicates that distinguished clause C is
mapped  onto distinguished  clause  D  by the  induced  distinguished
clause homomorphism.   Note that this implies that C.L is mapped onto
D.L by  the distinguished literal  homomorphism.   Also, C1,  C2 →  D
indicates that πboth distinguished
clauses, namely  C1 and C2,  are mapped onto  D by  the homomorphism.
Sometimes  we also indicate the  πlabels of the arcs  by drawing them
near the arcs; usually the labels are omitted. 

	Definition: A  πweak πhomomorphism  πof πtips  from  semantic
tree T1 to semantic tree T2 is a mapping f from the tips of T1 to the
tips   of  T2  which  satisfies  the   same  requirements  as  a  tip
homomorphism except that for a tip  node N of T1, the clause at  N in
T1 is only required to be a πsubset of the clause at f(N) in T2. 

	We can  similarly define weak  homomorphisms of distinguished
literals, weak  homomorphisms  of  distinguished  clauses,  and  weak
homomorphisms of mate pairs, with  the appropriate inducing relations
between them.   Note that the composition of any of the various kinds
of  homomorphisms,   including   the  weak   ones,   yields   another
homomorphism of the  same type.  Later we  shall characterize special
classes  of homomorphisms as compositions of  certain simple kinds of
homomorphisms. 

	Note that if T1 and  T2 are semantic trees and G1 and  G2 are
the distinguished  clause graphs of  T1 and T2,  respectively, then a
homomorphism of tips from T1 to T2 induces a mapping from G1 to  G2. 
The image of G1 under this mapping will be a subgraph of G2.  Similar
remarks apply to the mate pair graphs of T1 and T2. 

	Definition: An πautomorphism is a  homomorphism of a semantic
tree  T  into itself.    This applies  to  all the  various  kinds of
homomorphisms.    Thus  we  may  speak  of  a  distinguished  literal
automorphism,  and  so  on.    Later  we  will  show  that  any  weak
automorphism  of a complete semantic tree  without vacuous arcs is an
ordinary  automorphism.    Also,  we  will  show  that  any  ordinary
automorphism of such a tree must be the identity mapping. 

	Definition:  Semantic tree  T1  πcovers semantic  tree  T2 if
there is a distinguished literal homomorphism from the  distinguished
literals of  T2 πonto the  distinguished literals of  T1.   Note that
covering is transitive.  If Tf1 covers T2 then we say that T1 is less
than T2 in the covering ordering.   We might ask questions about  the
structure of the set of complete trees  over a set S of clauses which
are  minimal in  the covering ordering.   Note  that any homomorphism
between such trees will be a distinguished literal isomorphism. 

	Definition: Suppose P1 is a path of mate pairs  in a semantic
tree T1.   Suppose f is a distinguished  literal homomorphism from T1
to T2.  Then the πimage of P1 under f is the path P2 of mate pairs in
T2 in which  every mate pair is  the image of the  corresponding mate
pair  of T1.   That is, every  mate pair of  P2 is  obtained from the
corresponding  mate  pair  of  P1  by  replacing  both  distinguished
literals by their images under f. 

	Theorem  (Images  of  Continuous  Paths):   The  image  of  a
continuous   path  of  mate  pairs   under  a  distinguished  literal
homomorphism is continuous. 

	Proof:  Distinct   distinguished  literals   from  the   same
distinguished clause are mapped  onto distinct distinguished literals
from  the same  distinguished clause by  such a  homomorphism.  Also,
mate  distinguished  literals  are  mapped  into  mate  distinguished
literals by  such a homomorphism.   See figure 4.2 for  an example of
the image of a continuous path under a homomorphism. 

	Here  is  a   special  case   in  which   the  result   about
automorphisms being the identity is easy to prove:

	Theorem (Automorphisms of  Reduced Trees): There is  only one
distinguished  literal  automorphism of  a reduced  semantic  tree T,
namely, the identity mapping. 

	Proof: Consider what happens to distinguished literals at the
arcs  leading out  of the  root  of T.    They must  be mappped  onto
themselves since  no other arcs in T have the same labels as the arcs
leading out of  the root of T.   Also, all distinguished  literals in
the  left  subtree   of  T  (if  it  exists)   must  be  mapped  onto
distinguished literals in the  left subtree of  T by a  connectedness
argument, and similarly for the right subtree of T.  The theorem then
follows by induction.   Later we will extend this result to arbitrary
complete semantic trees without vacuous arcs. 

			Closed Sets

	Note that the image of  a connected set under a  homomorphism
is  always connected.   Later  we discuss  other classes  of sets  of
distinguished   literals  whose   behavior  under   homomorphisms  is
interesting.   Now  we introduce  one  of these  classes of  sets  of
distinguished literals, the πclosed sets. 

	Definition:  A πclosed  set  of distinguished  literals  in a
semantic tree T is a set  S of distinguished literals satisfying  the
following requirements:

	1.) Every element of S has at least one mate that is in S. 

	2.) If L1 is in S and L2 is in the same distinguished clause
	as L1, then L2 is in S. 

Note  that the  connected  component of  a  distinguished literal  is
closed,  in  a  complete semantic  tree  in  which all  distinguished
literals are matched. 

	Theorem  (Images of  Closed  Sets under  Homomorphisms):  The
image of a closed set of distinguished literals under a distinguished
literal homomorphism is closed. 

	Proof: Definition  of  distinguished  literal  homomorphism. 
Note that  the set of  distinguished literals in a  complete semantic
tree without vacuous arcs is closed, as is the empty set. 

	Theorem  (Closed  Sets and  Arcs):  Suppose T  is  a complete
finite semantic tree without vacuous arcs.  Then any non-empty closed
subset S of the distinguished literals of T must include at least one
distinguished literal from each arc of T. 

	Proof: By induction  on the  left and right  subtrees of  T. 
Consider  the  arcs leading  out  of  the  root.   Either  both  have
distinguished literals  that are in S, or neither  does.  If both do,
then at least one arc from the left and right subtrees of T (if these
subtrees  are non-empty)  must  have a  distinguished  literal in  S.
Therefore the theorem follows by induction.  If neither does, then at
least one  arc  from the  left  and right  subtrees  of T  (if  these
subtrees are non-empty) must  have πno distinguished literals from S.
Therefore the theorem again follows by induction.  Also, the  theorem
is trivially true for empty trees. 

	Corollary (Closed  Sets  and Complete  Trees without  Vacuous
Arcs): Any non-empty closed subset of a complete finite semantic tree
without vacuous arcs includes all distinguished literals in the tree. 

	Proof: Suppose T is such a tree and A is a maximal arc of T. 
Now, some  distinguished literal L  at A must be  in S, by  the above
theorem.    But all  distinguished literals  at  A are  from the  same
distinguished clause,  namely, the  distinguished clause  at the  tip
immediately above  the arc A.   Hence, by the  definition of a closed
set, all distinguished literals  from this distinguished clause  must
be in S.  But the same argument  applies to all distinguished clauses
of T. 

	Theorem (Homomorphisms between Complete Trees without Vacuous
Arcs): Suppose  f is a distinguished literal  homomorphism from T1 to
T2, where T1 and T2 are complete semantic trees without vacuous arcs.
Suppose  T1  is  non-empty.    Then  f  is  onto.    That  is,  every
distinguished   literal  of  T2   is  the  image  under   f  of  some
distinguished literal of T1. 

	Proof: The set of distinguished literals of T1  is closed and
non-empty, hence its image under f is closed and non-empty, hence its
image under f includes every distinguished literal of T2. 
Note that T2 covers T1 in this case.

	Corollary:  Any  distinguished  literal   automorphism  of  a
complete finite semantic tree without vacuous arcs is a permutation. 

	Note  that complete πreduced  semantic trees  have no vacuous
arcs, and so similar remarks apply to them. 

		Arc and Distinguished Literal Indices

	Now we consider  another aspect of homomorphisms  of semantic
trees. 

	Definition: Suppose f is a distinguished literal homomorphism
from T1 to T2.  Then the πindex under f of a distinguished  literal L
in T2 is the πnumber of distinguished literals in T1 mapped onto L by
f. 

	Theorem  (Non-Uniform Distinguished Literal Indices): Suppose
f is a distinguished literal homomorphism from T1 to T2, where T1 and
T2 are complete semantic trees without vacuous arcs.  Then one of the
following two conditions holds:

	1.)  Every distinguished literal in T2 has the same index under f.
	     In this case we say f is of πuniform πindex and we call this
	     index the πdistinguished πliteral πindex of f.

	2.)  For every index i such that some distinguished literal in T2
	     has index i under f,  there is some distinguished literal
	     L of T2 of index i such that no mate of L has index i.

	Proof:  Note  that  all  the   distinguished  literals  in  a
distinguished clause  of T2 will have the same  index under f.  Hence
if  condition  2  is  false  for  some  index  j,  then  the  set  of
distinguished literals of T2 of index  j is closed, hence condition 1
is  true.   Later we will  discuss the  question of  the existence of
homomorphisms of various distinguished literal indices. 

	Now  we discuss  a  relationship  between  homomorphisms  and
mappings of arcs of semantic trees.  In the process, we introduce the
concept of the πarc πindex of a homomorphism. 

	Definition:  A  mapping  f  of  distinguished  literals  from
semantic tree T1 to  semantic tree T2 is πarc πconsistent  if for all
arcs A  of T1, there exists  arc B of T2  such that all distinguished
literals at arc A of T1 are mapped onto distinguished literals at arc
B of T2. 

	Note  that all  distinguished  literal  homomorphisms from  a
complete semantic tree without vacuous arcs are arc consistent. 

	Definition: A  πmapping πof  πarcs from  semantic tree T1  to
semantic tree T2 is  a function mapping the arcs of T1 to the arcs of
T2. 

	Definition: Suppose f is a distinguished literal homomorphism
from  semantic  tree T1  to  semantic  tree T2.    Suppose  f is  arc
consistent.   Then the arc mapping πinduced by  f is the mapping g of
arcs from T1 to T2 such that for all arcs A  of T1, all distinguished
literals at A  are mapped by f to distinguished  literals at arc g(A)
of T2. 

	Definition: The πarc πindex of an arc B under a  homomorphism
f of distinguished  literals is the number  of arcs mapped onto  B by
the arc mapping induced by f. 

	Definition:  A  homomorphism  f  from  semantic  tree  T1  to
semantic tree T2 is of πuniform πarc πindex if all arcs in T2  are of
the same  index under f.   In this case  we call this index  the πarc
πindex of  f.  Later we will discuss the question of the existence of
homomorphisms  of  various  combinations  of  arc  and  distinguished
literal indices. 

	Finally, we  give a precise definition of  the term "trivial"
homomorphism. 

	Definition: Suppose f is a distinguished literal homomorphism
from semantic tree T1 to semantic tree T2.   Then f is πtrivial if it
is onto and if  for all distinguished literals L1 and L2 of T1, L1 is
above L2 in T1 iff f(L1) is above f(L2) in T2. 

	This concludes the  introductory sections.   Next we  discuss
paths of mate pairs in semantic trees.